/*
 * @lc app=leetcode.cn id=200 lang=typescript
 *
 * [200] 岛屿数量
 */

// @lc code=start

// 并查集
class UnionFind {
  parent: number[];
  size: number[];
  count: number;
  constructor(n: number = 0) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x: number): number {
    if (x === this.parent[x]) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x: number, y: number): void {
    let rx = this.find(x);
    let ry = this.find(y);
    if (this.size[rx] > this.size[ry]) {
      [rx, ry] = [ry, rx];
    }
    this.parent[rx] = ry;
    this.size[ry] += this.size[rx];
    this.count--;
  }
}
var numIslands = function (grid: string[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const unionFind = new UnionFind(m * n);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '0') continue;
      if (i > 0 && grid[i - 1][j] === '1') {
        unionFind.union(i * n + j, (i - 1) * n + j);
      }
      if (j > 0 && grid[i][j - 1] === '1') {
        unionFind.union(i * n + j, i * n + (j - 1));
      }
    }
  }

  let result = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 检查并查集里有几个符合的根就是结果
      if (grid[i][j] === '1' && unionFind.find(i * n + j) === i * n + j) {
        result++;
      }
    }
  }

  return result;
};
// @lc code=end
